//
// Created by 麻再挺 on 2021/1/28.
//

#include "double_linked_list.h"

/**
 * 创建双向链表
 * @param list 链表
 * @return
 */
Status DLinked_List_Create(DLinkedList *list) {
    // 申请内存
    list = (DLinkedList *) malloc(sizeof(DLinkedList));
    // 判断是否申请成功
    if (!list) return OVERFLOW;
    // 赋初始值
    // 前一结点
    list->prior = NULL;
    // 后一结点
    list->next = NULL;
    // 数据
    list->data = 0;
    return OK;
}

/**
 * 追加数据
 * @param list 链表
 * @param elem 数据
 * @return
 */
Status DLinked_List_Push(DLinkedList *list, ElemType elem) {
    // 临时变量
    DLinkedList *p = list;
    // 遍历查找最后一个结点
    while (p->next && p->next != list) {
        p = p->next;
    }
    // 创建新结点
    DLinkedList *s = (DLinkedList *) malloc(sizeof(DLinkedList));
    // 赋值
    // 赋值后一个结点
    s->next = list;
    // 赋值数据
    s->data = elem;
    // 赋值前一个结点
    s->prior = p;
    // 为前一个结点赋值后一个结点
    p->next = s;
    // 为头结点赋值前一个结点
    list->prior = s;
    return OK;
}

/**
 * 插入数据
 * @param list 链表
 * @param i 索引
 * @param elem 数据
 * @return
 */
Status DLinked_List_Insert(DLinkedList *list, int i, ElemType elem) {
    // 临时变量
    DLinkedList *p = list;
    // 临时索引
    int j = 0;
    // 遍历查找最后一个结点
    while (p->next && p->next != list && j < i) {
        // 获取下一个结点
        p = p->next;
        // 索引自加
        j++;
    }
    // 结点为空, 或者当前索引大于待删除位置
    if (p->next == list || j > i) return ERROR;
    // 创建新结点
    DLinkedList *s = (DLinkedList *) malloc(sizeof(DLinkedList));
    // 判断是否申请成功
    if (!s) return OVERFLOW;
    // 赋值数据
    s->data = elem;
    // 赋值下一结点
    s->prior = p;
    // 赋值前一结点
    s->next = p->next;
    // 赋值结点
    p->next = s;
    return OK;
}

/**
 * 将指向头结点的元素删除
 * @param list 列表
 * @return
 */
Status DLinked_List_Pop(DLinkedList *list) {
    // 临时变量
    DLinkedList *p = list;
    // 遍历查找最后一个结点
    while (p->next && p->next->next && p->next->next != list) {
        p = p->next;
    }
    // 移除最后一个结点
    p->next = list;
    return OK;
}

/**
 * 删除指定索引数据
 * @param list 列表
 * @param i 索引
 * @return
 */
Status DLinked_List_Delete(DLinkedList *list, int i) {
    // 临时变量
    DLinkedList *p = list;
    // 临时索引
    int j = 0;
    // 遍历查找最后一个结点
    while (p->next && p->next != list && j < i) {
        // 获取下一个结点
        p = p->next;
        // 索引自加
        j++;
    }
    // 结点为空, 或者当前索引大于待删除位置
    if (p->next == list || j > i) return ERROR;
    // 移除下一个结点
    p->next = p->next->next;
    return OK;
}

/**
 * 根据索引获取链表数据
 * @param list 链表
 * @param i 索引
 * @param node 数据
 * @return
 */
Status DLinked_List_Get_Elem(DLinkedList *list, int i, DLinkedList *node) {
    // 临时变量
    DLinkedList *p = list;
    // 临时索引
    int j = 0;
    // 遍历查找最后一个结点
    while (p->next && p->next != list && j < i) {
        // 获取下一个结点
        p = p->next;
        // 索引自加
        j++;
    }
    // 结点为空, 或者当前索引大于待删除位置
    if (p->next == list || j > i) return ERROR;
    // 赋值
    *node = *p->next;
    return OK;
}

/**
 * 合并两个线性链表, 合并后将值赋值到第一个链表中
 * @param list1 待合并线性链表
 * @param list2 待合并线性链表
 * @return
 */
Status DLinked_List_Merge(DLinkedList *list1, DLinkedList *list2) {
    // 赋值临时变量
    DLinkedList *pa = list1->next, *pb = list2->next, *pc = list1;
    // 循环合并
    while (pa->next != list1 && pb->next != list2) {
        // 判断值的大小
        if (pa->data < pb->data) {
            // 赋值前一项
            pc->prior = pa->prior;
            // 赋值
            pc->next = pa;
            // 移动
            pc = pa;
            // 移动到下一个
            pa = pa->next;
        } else {
            // 赋值前一项
            pc->prior = pb->prior;
            // 赋值
            pc->next = pb;
            // 移动
            pc = pb;
            // 移动到下一个
            pb = pb->next;
        }
    }
    // 赋值剩余数据
//    pc->next = pa ? pa : pb;
    if (pa->next != list1) {
        // 赋值前一项
        pc->prior = pa->prior;
        // 赋值剩余数据
        pc->next = pa;
    } else {
        while (pb->next == list2) {
            // 赋值前一项
            pc->prior = pb->prior;
            // 赋值下一结点
            pc->next = pb;
            // 移动pc
            pc = pb;
            // 获取下一个
            pb = pb->next;
        }
        // 赋值最后一项
        pb->next = list1;
        // 赋值前一项
        list1->prior = pb;
    }

    return OK;
}

/**
 * 打印循环链表数据
 * @param list 链表
 */
void DLinked_List_Print(DLinkedList *list) {
    // 赋值临时变量
    DLinkedList *p = list->next;
    // 遍历打印
    while (p && list != p) {
        printf("%d\t", p->data);
        // 获取下一个结点
        p = p->next;
    }
    printf("\n");
}